/*
*
给你一个下标从 0 开始长度为 n 的整数数组 buses ，其中 buses[i] 表示第 i 辆公交车的出发时间。同时给你一个下标从 0 开始长度为 m 的整数数组 passengers ，其中 passengers[j] 表示第 j 位乘客的到达时间。所有公交车出发的时间互不相同，所有乘客到达的时间也互不相同。

给你一个整数 capacity ，表示每辆公交车 最多 能容纳的乘客数目。

每位乘客都会搭乘下一辆有座位的公交车。如果你在 y 时刻到达，公交在 x 时刻出发，满足 y <= x  且公交没有满，那么你可以搭乘这一辆公交。最早 到达的乘客优先上车。

返回你可以搭乘公交车的最晚到达公交站时间。你 不能 跟别的乘客同时刻到达。

注意：数组 buses 和 passengers 不一定是有序的。

示例 1：

输入：buses = [10,20], passengers = [2,17,18,19], capacity = 2
输出：16
解释：
第 1 辆公交车载着第 1 位乘客。
第 2 辆公交车载着你和第 2 位乘客。
注意你不能跟其他乘客同一时间到达，所以你必须在第二位乘客之前到达。
示例 2：

输入：buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
输出：20
解释：
第 1 辆公交车载着第 4 位乘客。
第 2 辆公交车载着第 6 位和第 2 位乘客。
第 3 辆公交车载着第 1 位乘客和你。

提示：

n == buses.length
m == passengers.length
1 <= n, m, capacity <= 105
2 <= buses[i], passengers[i] <= 109
buses 中的元素 互不相同 。
passengers 中的元素 互不相同 。

  - @author ala
  - @date 2024-09-18 10:47
*/
package main

import (
	"fmt"
	"sort"
)

func main() {
	//buses, passengers := []int{10, 20}, []int{2, 17, 18, 19}
	//capacity := 2

	//buses, passengers := []int{20, 30, 10}, []int{19, 13, 26, 4, 25, 11, 21}
	//capacity := 2

	//buses, passengers := []int{2}, []int{2}
	//capacity := 2

	buses, passengers := []int{3}, []int{2, 4}
	capacity := 2

	fmt.Println(latestTimeCatchTheBus(buses, passengers, capacity))
}

func latestTimeCatchTheBus(buses []int, passengers []int, capacity int) int {
	return V1(buses, passengers, capacity)
}

/**
 *	1）buses，passengers 升序排列
 *	2）遍历 passengers，同时队列记录当前要上车的人
 *	3）如果 pi >= bi，则发车，队列出队 capacity 个
 *	4）如果是最后一辆车
 *		如果 queue 没过 capacity，继续往后装 capacity 个 或者 装到 pi > bi 为止
 *		如果 queue 依然没过 capacity，直接返回最后一趟车的 到达时间
 *		如果 queue 超过 capacity，则从 ql + capacity - 1 开始往前倒，找第一个断掉的位置
 */
func V1(buses []int, passengers []int, capacity int) int {
	//	公交车 和 等车人 按到达时间升序
	//bidx, pidx := sortIdxArray(buses), sortIdxArray(passengers)
	sort.Ints(buses)
	sort.Ints(passengers)

	//	前面的公交车直接装车走人，只留下最后一个
	bi, pi := 0, 0
	queue := make([]int, len(passengers))
	ql, qr, qs := 0, -1, 0
	for len(buses) > 1 && pi < len(passengers) {
		p := passengers[pi]
		if p <= buses[bi] {
			qr++
			queue[qr] = p
			qs++
			pi++
		}
		if p >= buses[bi] {
			c := 0
			for qs > 0 && c < capacity {
				ql++
				qs--
				c++
			}
			bi++
			if bi == len(buses)-1 {
				break
			}
		}
	}
	//	如果当前等车人不够 capacity 个，继续装人
	for pi < len(passengers) && qs < capacity {
		p := passengers[pi]
		pi++
		if p <= buses[bi] {
			qr++
			queue[qr] = p
			qs++
		} else {
			break
		}
	}
	//	如果没人在等车，直接返回最后一辆车的到站时间
	if qs == 0 {
		return buses[len(buses)-1]
	}
	//	如果等车人数仍不够 capacity，则判断 qr 是否等于 buses[-1]，若不等于，直接返回buses[-1]，否则从qr开始往前倒
	if qs < capacity {
		if queue[qr] != buses[len(buses)-1] {
			return buses[len(buses)-1]
		} else {
			for qr > 0 && queue[qr]-1 == queue[qr-1] {
				qr--
			}
			return queue[qr] - 1
		}
	} else {
		//	从qr开始往前倒，找第一个断掉的位置
		qr = ql + capacity - 1
		for qr > 0 && queue[qr]-1 == queue[qr-1] {
			qr--
		}
		return queue[qr] - 1
	}
}

func sortIdxArray(arr []int) []int {
	res := make([]int, len(arr))
	for i := 0; i < len(arr); i++ {
		res[i] = i
	}
	sort.Slice(res, func(i, j int) bool {
		return arr[res[i]] < arr[res[j]]
	})
	return res
}
